import java.util.ArrayList;
import java.util.List;

public class demo9 {
    //根据这个来判断是属于哪个框中的
    static List<int[]> list;
    //根据这个来判断那一个框中的数字已经有了
    static boolean[][] visit;
    //根据这个来判断某一行的某个数字是否已经出现
    static boolean[][] row;
    //根据这个来判断某一列的某个数字书否已经出现
    static boolean[][] col;
    public static void main(String[] args) {
        list=new ArrayList<>();
        //将各个板块的下标对应到数组的0-35的洗标，当下标/6就获得当前板块的下标
        //从左到右，从上到下分别为板块0.1.2.3.4.5
        list.add(new int[]{0,0});list.add(new int[]{0,1});list.add(new int[]{0,2});list.add(new int[]{1,0});list.add(new int[]{1,1});list.add(new int[]{2,0});
        list.add(new int[]{0,3});list.add(new int[]{0,4});list.add(new int[]{0,5});list.add(new int[]{1,2});list.add(new int[]{1,3});list.add(new int[]{1,4});
        list.add(new int[]{2,1});list.add(new int[]{2,2});list.add(new int[]{2,3});list.add(new int[]{3,0});list.add(new int[]{3,1});list.add(new int[]{4,0});
        list.add(new int[]{1,5});list.add(new int[]{2,4});list.add(new int[]{2,5});list.add(new int[]{3,2});list.add(new int[]{3,3});list.add(new int[]{3,4});
        list.add(new int[]{4,1});list.add(new int[]{4,2});list.add(new int[]{4,3});list.add(new int[]{5,0});list.add(new int[]{5,1});list.add(new int[]{5,2});
        list.add(new int[]{3,5});list.add(new int[]{4,4});list.add(new int[]{4,5});list.add(new int[]{5,3});list.add(new int[]{5,4});list.add(new int[]{5,5});
        //实例化七个是因为要直接对应数字1-6，不用再去减一；
        visit=new boolean[6][7];
        row=new boolean[6][7];
        col=new boolean[6][7];

        //创建一个如图所示的数独，','表示为空，否则填数据
        //初始化数组
        char[][] board=new char[6][6];
        board[0][0]='1';board[0][3]='4';board[0][5]='2';board[1][0]='2';board[1][1]='3';board[2][1]='1';board[2][3]='2';
        board[3][2]='2';board[3][4]='1';board[4][4]='4';board[4][5]='5';board[5][0]='5';board[5][2]='4';board[5][5]='1';
        for(int i=0;i<6;i++){
            for(int j=0;j<6;j++){
                if(board[i][j]<'0'||board[i][j]>'9')
                    board[i][j]=',';
            }
        }

        //初始化行列板块是否某些出现的数字
        for(int i=0;i<6;i++){
            for(int j=0;j<6;j++){
                char ch=board[i][j];
                int index=getBoardIndex(list,i,j);
                //如果当前字符不是','，就表示有数字
                if(ch!=','){
                    //有数字就要把某行某列的某个板块的数字确定为true
                    //ch-'0'就等于数字，例如ch=='1'，减去'0'就等于1；
                    row[i][ch-'0']=col[j][ch-'0']=visit[index][ch-'0']=true;
                }
            }
        }
        dfs(board);

        for(int i=0;i<6;i++){
            for(int j=0;j<6;j++){
                System.out.print(board[i][j]+" ");
            }
            System.out.println();
        }

    }

    //利用递归+回溯的方式去解决
    public static boolean dfs(char[][] board){

        for(int i=0;i<board.length;i++){
            for(int j=0;j<board[0].length;j++){
                //如果当前不是','就要填数字
                if(board[i][j]==','){
                    int index=getBoardIndex(list,i,j);
                    int k=0;
                    for(k=1;k<=6;k++){
                        if(!row[i][k] && !col[j][k] && !visit[index][k]){
                            board[i][j]=(char)(k+'0');
                            row[i][k]=col[j][k]=visit[index][k]=true;
                            boolean flag=dfs(board);
                            if(!flag){
                                board[i][j]=',';
                                row[i][k]=col[j][k]=visit[index][k]=false;
                            }else{
                                return true;
                            }
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
    //根据i，j去对应以获得板块的下标，0-5
    private static int getBoardIndex(List<int[]> list, int i, int j) {
        for(int index=0;index<list.size();index++){
            int[] temp=list.get(index);
            if(temp[0]==i&&temp[1]==j) return index/6;
        }
        return -1;
    }
}
